#include <set>
#include <iostream>

using namespace std;

// 快乐数
// 1.1 下一个数位平方和数是多少？
int getNext(int n) {
  int result = 0;

  while (n != 0) {
    result += (n % 10) * (n % 10);
    n /= 10;
  }

  return result;
}

// 1.2 寻找快乐数？
// 判断 n 是否是一个快乐数，结果有几种情况？
// 如果 getNext 收敛到 1 => n 是一个快乐数
// 如果两次 getNext 的结果相同 => n 不是快乐数

// 是否存在 n 在计算的过程中，不断变得越来越大，越来越大，进而导致 n 不是一个快乐数？
// 9    => 81
// 99   => 162
// 999  => 243 一个三位数，它的平方数位和最大也就是个三位数
// 9999 => 324 一个四位数，它的平方数位和一定会比原来少一位
// ...
// 9999999999999 => 1053 一个十三位数，它的平方数位和就会丢失很多位
//
// 随着 n 不断的增大，n 越大，平方数位和丢失掉的位数就越多。
//
// 对于任意的一个 n 来说，如果我们不断的对它求平方数位和，那么这个和的位数一定是越来越少的。
// 那么在这个不断位数降低的过程中：
// 要么最终减少到 1
// 要么减少到发生循环
//
// 每找到一个不是快乐数的数字，那么它一定就对应着一个快乐数环。
// 那我们就有办法这个环上的数字提取出来。
// 我们只要在 1 ~ 999 这个范围里，查找所有的快乐数环。
//

// 4 => 16 => 37 => 58 => 89 => 145 => 42 => 20 => 4
bool isHappyNumber(int n) {
  if (n == 1) {
    return true;
  }

  set<int> results {n};
  int s = getNext(n);

  while (s != 1) {
    // 判断 s 是否在 results 里
    if (results.find(s) != results.end()) {
      return false;
    }

    results.insert(s);
    s = getNext(s);
  }
  
  return true;
}

bool isHappyNumber1(int n) {
  int slow = n;
  int fast = getNext(n); 

  while (fast != 1 && slow != fast) {
    slow = getNext(slow);
    fast = getNext(fast);
    fast = getNext(fast);
  }

  if (fast == 1) {
    return true;
  }
  else {
    return false;
  }
}


int main(int argc, char const *argv[])
{
  /* code */
  return 0;
}
